package chapter15;

/**
 * @author : DuJiabao
 * @Date : 2021/2/22 11:01
 * @Project : thinking_in_java
 * @File : null.java
 * @Desc :
 */
public class LinkedStack<T> {
  // 内部类，节点
  private class Node<U> {
    U item;
    Node<U> next;  // 下一个节点

    // 构造器，设置值及下一个节点
    public Node(U item, Node<U> next) {
      this.item = item;
      this.next = next;
    }

    public Node() {
      this.item = null;
      this.next = null;
    }

    //判断是否为空，即最后一个节点
    boolean end() {
      return item == null && next == null;
    }
  }

  private Node<T> top = new Node<>();  // top指向末端哨兵。后面top一直往后移动，指向栈顶。该节点就是一直存在于栈底，叫做末端哨兵

  public void push(T item) {
    top = new Node<T>(item, top);  // 新节点指向栈顶。top移动，指向最新节点，即栈顶
  }

  public T pop() {
    T item = top.item;  // 获取当前栈顶元素
    if (!top.end())  // 如果不是最后一个，那么还有会next，将top移动到next
      top = top.next;
    return item;  // 返回当前栈顶元素
  }

  public static void main(String[] args) {
    LinkedStack<String> stack = new LinkedStack<>();
    for (String s : "hello world ni hao shi jie".split(" ")) {
      stack.push(s);  // 遍历push
    }

    String s;
    // 遍历pop，直到末端哨兵
    while ((s = stack.pop()) != null) {
      System.out.println(s);
    }
  }
}
